// DFS 递归 - 前序遍历
func maxDepth3(root *TreeNode) int {
    var res = 0

    var preOrder func(*TreeNode, int)
    preOrder = func(node *TreeNode, currDepth int) {
        if node == nil {
            return
        }

        if node.Left == nil && node.Right == nil {
            if currDepth > res {
                res = currDepth
            }
        }

        preOrder(node.Left, currDepth + 1)
        preOrder(node.Right, currDepth + 1)
    }

    preOrder(root, 1)

    return res
}


// DFS 递归 - 后序遍历
// 计算以 root 为根节点的二叉树的最大深度
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    var leftMaxDepth = maxDepth(root.Left)
    var rightMaxDepth = maxDepth(root.Right)

    if (leftMaxDepth > rightMaxDepth) {
        return leftMaxDepth + 1
    } else {
        return rightMaxDepth + 1
    }
}